Hiện nay mọi thuật toán cho các bài toán NP-đầy đủ đều đòi hỏi thời gian lớn hơn đa thức của kích thước dữ liệu vào, và cũng không rõ liệu có tồn tại thuật toán nhanh hơn hay không.

Các phương pháp sau đây thường được áp dụng để giải quyết các bài toán tính toán nói chung, và trong nhiều trường hợp dẫn đến thuật toán nhanh hơn.

• Thuật toán xấp xỉ: Thay vì tìm kiếm lời giải tối ưu, chỉ cần tìm một lời giải "gần" tối ưu.
• Thuật toán ngẫu nhiên: Sử dụng bit ngẫu nhiên để giảm thời gian chạy trung bình, và cho phép thuật toán thất bại với một xác suất nhỏ (xem phương pháp Monte Carlo)
• Hạn chế: giải quyết một số trường hợp đặc biệt của dữ liệu vào bằng các thuật toán đặc biệt cho các trường hợp đó (ví dụ như đồ thị phẳng, điểm trong không gian Euclide).
• Độ phức tạp tham số: đưa ra thêm một số tham số, nếu trong trường hợp đặc biệt các tham số này là nhỏ thì thời gian chạy cũng nhanh hơn.
• Heuristic: có những thuật toán làm việc khá tốt trong nhiều trường hợp nhưng chưa thể chứng minh được chúng luôn cho kết quả tốt trong mọi trường hợp.